#include <vector>
using namespace std;
class Solution
{
public:
    int singleNonDuplicate(vector<int> &nums)
    {
        if (nums.size() == 1)
            return nums[0];
        int l(0), r(nums.size() - 2);
        if (nums[r] != nums[r + 1])
            return nums[r + 1];
        // 更复杂的二分 需要基于mid的奇偶来判断指针更新条件
        while (l < r)
        {
            int mid = (l + r) >> 1;
            if (mid % 2)
                if (nums[mid] == nums[mid + 1])
                    r = mid;
                else
                    l = mid + 1;
            else if (nums[mid] == nums[mid + 1])
                l = mid + 2;
            else
                r = mid;
        }
        return nums[l];
    }
};